package Search.BST_Map;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/13 14:52
 */
public class BSTreeMap {
    private TreeNode root;
    private int size;

    public BSTreeMap() {
        this.root = null;
        this.size = 0;
    }

    public String put(Long key, String value) {
        // 1. 插入  搜索树中没有这个 key 时，返回 null
        // 2. 更新  搜索树中有这个 key 时，返回原来的 value
        TreeNode node = new TreeNode(key, value);

        if (root == null) {
            root = node;
            this.size = 1;
            return null;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        int c = -1;
        while (cur != null) {
            c = key.compareTo(cur.key);
            if (c == 0) {
                String oldValue = cur.value;
                cur.value = value;
                return oldValue;
            } else if (c < 0) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        if (c < 0) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        size++;

        return null;
    }

    public String get(Long key) {
        TreeNode cur = root;
        while (cur != null) {
            int c = key.compareTo(cur.key);
            if (c == 0) {
                return cur.value;
            } else if (c < 0) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        BSTreeMap map = new BSTreeMap();
        map.put(1L, "一");
        map.put(2L, "二");
        map.put(30L, "三十");

        System.out.println(map.get(1L));
    }
}
